# 反转字符串里的单词: https://leetcode-cn.com/problems/reverse-words-in-a-string/

# 官方解题，使用队列
import collections

class Solution:
    def reverseWords(self, s: str) -> str:
        """ 使用双端队列，隔离出每个单词后，头部插入 再转字符串"""
        left, right = 0, len(s) - 1
        # 去掉字符串开头的空白字符
        while left <= right and s[left] == ' ':
            left += 1
        
        # 去掉字符串末尾的空白字符
        while left <= right and s[right] == ' ':
            right -= 1
            
        d, word = collections.deque(), []
        # 将单词 push 到队列的头部
        while left <= right:
            if s[left] == ' ' and word:
                d.appendleft(''.join(word))
                word = []
            elif s[left] != ' ':
                word.append(s[left])
            left += 1
        d.appendleft(''.join(word))
        
        return ' '.join(d)


# 在Python中字符串的直接拼接，好像要快一点
class Solution:
    def reverseWords(self, s: str) -> str:
        """
            和双端队列同样的原理，头部拼接字符串。直接找到每一个单词，拼接就好了
        """
        n = len(s)
        word = ''
        rst = ''
        # 1. 首先去掉字符串两边的空格
        i, j = 0, n - 1
        while s[i] == ' ': i += 1 
        while s[j] == ' ': j -= 1

        # 二，找出每个单词进行拼接，也是头部拼接
        for i in range(i, j + 1):
            # 拼接单词
            if s[i] != ' ':
                word += s[i]
            # 拼接反转字符串， 碰到空格 且 word 不是空字符串，就拼接
            if s[i] == ' ' and word:
                rst = ' ' + word + rst
                word = ''
        
        # 最后还剩一个单词没加进去，不需要加空格了
        return word + rst        



